package com.guoba;

/**
 * 二分查找练习
 *
 * Params:  a -待查找的升序数组
 *          target-带查找的目标值
 *
 * Returns:
 *          找到则返回索引
 *          找不到则返回-1
 */
public class BinarySearch {
    /**
     * 简单实现
     * @param a 待查找的升序数组
     * @param target  带查找的目标值
     * @return 找到则返回索引  找不到则返回-1
     */
    public static int binarySearchBasic(int[] a,int target){
        int i =0,j= a.length-1;//设置指针和初始值
        while (i<=j){//定义指针查找范围
            //int m = (i+j)/2;//中间索引 存在问题，当索引值较大时，相加之后超过int范围变为负数，再除2已无意义
            int m = (i+j) >>> 1;//中间索引 改为无符号右移 问题解决
            if (a[m]>target){
                j=m-1;
            }else if (a[m]<target){
                i=m+1;
            }else {
                return m;
            }
        }
        return -1;
    }
    /**
     * 二分法查找元素索引说明：
     * 首先设置了两对指针，指向数组的两端，当i还在j的左侧时，或是他俩相交的时候，
     * 就循环来执行里面的逻辑
     * 当i跑到j的右侧时，说明没有找到对应元素的索引，返回-1。
     * 否则进入中间的循环，先计算得到中间索引，
     * 然后将中间索引和目标值进行比较
     * 如果目标值在中间索引的左侧，说明应该在左侧继续查找，所以将右边索引改为中间值减一
     * 否则就从右边进行查找，将左边索引改为中间值加一。
     * 除了以上两种情况则说明符号寻找条件，返回相应的索引即可。
     * 若一次找不到，则进行循环，按照以上规律直到找到为止。
     * 若一直找不到，则会因为循环条件不满足而停止循环
     */

    public static void main(String[] args) {
        int[] a = {7,13,21,30,36,44,52,53};
        System.out.println(binarySearchBasic(a, 21));//返回查找元素的索引 找不到则返沪-1
    }
}
